1. Field of the Invention
The present invention relates to displacement estimation, and more specifically, to displacement estimation for an optical mouse using a predicted velocity.
2. Description of the Related Art
A pointing device such as mouse is a standard peripheral for a computer system. A mechanical mouse typically has rollers, wheels, or the like, that contact a rubber-surfaced steel ball at the equator thereof and convert the rotation of the ball into electrical signals. The mechanical mouse has a number of shortcomings such as deterioration or damage to the surface of the mouse ball and mouse pad, resulting from the mechanical construction and operation thereof that rely to a significant degree on a fairly delicate compromise among the mechanical forces involved. An optical mouse utilizes optical and electronic method to compute the movement of the mouse, and is a popular replacement for the mechanical mouse. Compared with the conventional mechanical mouse, an optical mouse offers better reliability and performance. Thus optical pointing devices have captured a significant share of the mouse market.
An optical mouse typically has a logical operation circuit and a Complementary Metal Oxide Semiconductor (CMOS) photosensing array comprising photo detectors. The CMOS photosensing array sequentially captures images of the area in which the optical mouse moves and generates digital signals representing the captured image. The digital image varies with the movement of the optical mouse. The logical operation circuit computes the displacement of the optical mouse according to the dynamic change in the digital image, and directs the computer to control the pointer (cursor) on the screen in accordance with movement of the mouse.
The displacement of the optical mouse is commonly tracked and estimated by block matching. Block matching is accomplished by comparing a newly captured sample frame (current frame) with a previously captured reference frame (template frame) to ascertain the direction and amount of movement. Conventional block matching performs a fully search pf block with a predetermined size. As shown in FIG. 1, the template frame 100 and current frame 104 are digital images of a 6*6 pixel area. If these two digital images are fully searched using a 2*2 pixel block, the computer must perform 25*25 (625) correlation computations. If two digital images of 16*16 pixels are fully searched with an 8*8 pixel block, the computer must perform 81*81 (6561) correlation computations.
The number of correlation computations can be greatly reduced if a template block in the template frame is used for block matching instead of the full searching process. As shown in FIG. 1, a 2*2 template block 102 is located in the center of the template frame 100. Accordingly, the computer only needs to perform 5*5 (25) correlation computations for the current frame 104 when using the 2*2 block as a search unit. Block matching determines a block with the least difference (greatest correlation) after comparing all the 2*2 blocks (from block 106 to block 108) in the current frame 104 with the template block 102. Note that the searching order is not limited to the described order. If two digital images with 16*16 pixels are searched with an 8*8 pixel block, a total of 9*9 (81) correlation computations must be performed. Although the use of template block significantly reduces the number of searching and computation cycles, a large size image still requires long computation time to compare each block with the template block. Furthermore, performing a fully search using a template block also requires a large amount of memory and processor capacity for large digital images.